/*
 * @lc app=leetcode.cn id=3 lang=typescript
 *
 * [3] 无重复字符的最长子串
 */

// @lc code=start
function lengthOfLongestSubstring(s: string): number {
  // 验证长度为len，能否找到无重复的字串
  const isValida = (len: number, s: string): boolean => {
    const hash = new Array(256).fill(0);
    let k = 0;
    for (let i = 0; i < s.length; i++) {
      const idx = s.charCodeAt(i);
      if (hash[idx] === 0) k++;
      hash[idx] += 1;
      if (i >= len) {
        const idx = s.charCodeAt(i - len);
        hash[idx] -= 1;
        if (hash[idx] === 0) k--;
      }
      if (k === len) return true;
    }
    return false;
  };

  if (s.length === 0) return 0;

  let head = 1;
  let tail = s.length;
  let mid: number;
  while (head < tail) {
    // 二分查找区间长度
    mid = head + ((tail - head + 1) >> 1);
    if (isValida(mid, s)) head = mid;
    else tail = mid - 1;
  }

  return head;
}
// @lc code=end
